from typing import List


class Solution:
    def getMaxMatrix(self, matrix: List[List[int]]) -> List[int]:
        m = len(matrix)
        n = len(matrix[0])

        def getMax(nums):
            prev = nums[0]
            l = 0
            r = 0
            left = 0
            right = 0
            ans = nums[0]
            for i in range(1, n):
                r += 1
                if prev >= 0:
                    prev += nums[i]
                    r = i
                else:
                    prev = nums[i]
                    l = r
                if ans < prev:
                    ans = prev
                    left = l
                    right = r
            return left, right, ans

        ans = matrix[0][0]
        r1 = 0
        c1 = 0
        r2 = 0
        c2 = 0
        for i in range(m):
            arr = matrix[i]
            for j in range(i, m):
                if j > i:
                    for k in range(n):
                        arr[k] += matrix[j][k]
                ai, aj, anss = getMax(arr)
                if anss > ans:
                    ans = anss
                    r1 = i
                    c1 = ai
                    r2 = j
                    c2 = aj
        return [r1, c1, r2, c2]


if __name__ == '__main__':
    s = Solution()
    r = s.getMaxMatrix([[-1, 0], [0, -1]])
    print(r)
